package com.zyk.grate_offer.class07;

/**
 * 非负数组中, 求哪儿两个数与的结果最大
 *
 * @author zhangsan
 * @date 2021/5/15 11:20
 */
public class Code01_MaxAndVal {

    // ×: O(N), 先用前缀树做, 空间复杂度高. 不能用前缀树. 因为如果这一位为0, 那么和&0 &1 都为0,不知道该往那儿边走.

    // 暴力解
    public static int maxAndVal1(int[] arr) {
        int max = Integer.MIN_VALUE, N = arr.length;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                max = Math.max(max, arr[i] & arr[j]);
            }
        }
        return max;
    }

    public static int maxAndVal2(int[] arr) {
        int M = arr.length;     // 淘汰区
        int ans = 0;
        for (int bit = 30; bit >= 0; bit--) {
            int i = 0;
            int tmp = M;
            while (i < M) {
                if ((arr[i] >> bit & 1) == 1) {
                    i++;
                } else {
                    swap(arr, i, --M);
                }
            }
            if (M == 2) {
                return arr[0] & arr[1];
            } else if (M < 2) {
                M = tmp;
            } else {
                ans |= (1 << bit);
            }
        }
        return ans;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int maxSize = 50;
        int range = 30;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int size = (int) (Math.random() * maxSize) + 2;
            int[] arr = randomArray(size, range);
            int ans1 = maxAndVal1(arr);
            int ans2 = maxAndVal2(arr);
            if (ans1 != ans2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束");

    }

    public static int[] randomArray(int size, int range) {
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = (int) (Math.random() * range) + 1;
        }
        return arr;
    }


}
